#include <vector>
#include <algorithm>
using namespace std;

class Solution {
public:
    int countPairs(vector<int>& nums, int target) {
        sort(nums.begin(), nums.end());
        int res = 0;
        int n = nums.size();

        for (int i = 0; i < n - 1; i++) {
            int left = i + 1;
            int right = n - 1;
            int pos = n; // 默认找不到则返回末尾

            // 手写二分查找第一个 >= target - nums[i] 的位置
            while (left <= right) {
                int mid = left + (right - left) / 2;
                if (nums[mid] >= target - nums[i]) {
                    pos = mid;
                    right = mid - 1;
                } else {
                    left = mid + 1;
                }
            }

            res += (pos - i - 1); // pos 左边的所有元素与 nums[i] 之和 < target
        }

        return res;
    }
};
